package graph

import (
	"fmt"
	"sort"
)

type TreeNode[T any] struct {
	InSet  map[*TreeNode[T]]struct{}
	OutSet map[*TreeNode[T]]struct{}
	Value  T
}

func (t *TreeNode[T]) String() string {
	return fmt.Sprintf("%+v", t.Value)
}

func (t *TreeNode[T]) GoString() string {
	return t.String()
}

func NewTreeNode[T any](value T) *TreeNode[T] {
	return &TreeNode[T]{Value: value, InSet: make(map[*TreeNode[T]]struct{}), OutSet: make(map[*TreeNode[T]]struct{})}
}

type Graph[T any] struct {
	Nodes       map[*TreeNode[T]]struct{}
	CompareFunc func(a, b T) bool
}

func NewGraph[T any](compareFunc func(a, b T) bool) *Graph[T] {
	return &Graph[T]{CompareFunc: compareFunc}
}

func (g *Graph[T]) AddNode(node *TreeNode[T]) {
	g.Nodes[node] = struct{}{}
}

func (g *Graph[T]) AddDepend(who *TreeNode[T], beDepend *TreeNode[T]) {
	beDepend.OutSet[who] = struct{}{}
	who.InSet[beDepend] = struct{}{}
}

func (g *Graph[T]) findNextToOutput(in map[*TreeNode[T]]struct{}) *TreeNode[T] {
	availableSet := make([]*TreeNode[T], 0, 16)
	for node := range in {
		if len(node.InSet) == 0 {
			availableSet = append(availableSet, node)
		}
	}
	sort.Slice(availableSet, func(i, j int) bool {
		return g.CompareFunc(availableSet[i].Value, availableSet[j].Value)
	})
	if len(availableSet) > 0 {
		return availableSet[0]
	}
	return nil
}

func (g *Graph[T]) GenOutPut() []T {
	ret := make([]T, 0, len(g.Nodes))
	for {
		outputNode := g.findNextToOutput(g.Nodes)
		if outputNode == nil {
			break
		}
		ret = append(ret, outputNode.Value)
		delete(g.Nodes, outputNode)
		for outNode := range outputNode.OutSet {
			delete(outNode.InSet, outputNode)
			delete(outputNode.OutSet, outNode)
		}
	}
	if len(g.Nodes) != 0 {
		for n := range g.Nodes {
			fmt.Printf("%s:\n", n.Value)
			for k := range n.InSet {
				fmt.Printf("\t%+v\n", k.Value)
			}
		}
		panic("import circle")
	}
	return ret
}
